package queue

import (
	"errors"
	"fmt"
	"strings"
)

// Deque 双端队列
type Deque[E any] struct {
	data        []E
	front, tail int
	size        int
}

func MakeDeque0[E any](capacity int) *Deque[E] {
	return &Deque[E]{
		data: make([]E, capacity, capacity), //不浪费空间
	}
}

func MakeDeque[E any]() *Deque[E] {
	return MakeDeque0[E](10)
}

func (d *Deque[E]) IsEmpty() bool {
	return d.size == 0
}
func (d *Deque[E]) GetSize() int {
	return d.size
}

func (d *Deque[E]) GetCap() int {
	return cap(d.data)
}

func (d *Deque[E]) GetFront() (E, error) {
	var zero E
	if d.IsEmpty() {
		return zero, errors.New("queue is empty")
	}
	return d.data[d.front], nil
}

func (d *Deque[E]) GetLast() (E, error) {
	var zero E
	if d.IsEmpty() {
		return zero, errors.New("queue is empty")
	}
	return d.data[(d.tail+d.GetCap()-1)%d.GetCap()], nil
}

func (d *Deque[E]) AddFront(e E) {
	//容量满,1倍扩容
	if d.size == d.GetCap() {
		d.resize(2 * d.GetCap())
	}
	d.front = (d.front + d.GetCap() - 1) % d.GetCap()
	d.data[d.front] = e
	d.size++
}
func (d *Deque[E]) AddLast(e E) {
	//容量满,1倍扩容
	if d.size == d.GetCap() {
		d.resize(2 * d.GetCap())
	}
	d.data[d.tail] = e
	d.tail = (d.tail + 1) % d.GetCap()
	d.size++
}

func (d *Deque[E]) RemoveFront() (E, error) {
	var zero E
	if d.IsEmpty() {
		return zero, errors.New("cannot remove front from an empty queue")
	}
	e := d.data[d.front]
	d.data[d.front] = zero
	d.front = (d.front + 1) % d.GetCap()
	d.size--
	//1/4容量,缩容1/2，缩容容量不能为0，否则无法扩容
	if d.size == d.GetCap()/4 && d.GetCap()/2 != 0 {
		d.resize(d.GetCap() / 2)
	}
	return e, nil
}

func (d *Deque[E]) RemoveLast() (E, error) {
	var zero E
	if d.IsEmpty() {
		return zero, errors.New("cannot remove front from an empty queue")
	}
	e := d.data[d.tail]
	d.data[d.tail] = zero
	d.tail = (d.tail + d.GetCap() - 1) % d.GetCap()
	d.size--
	//1/4容量,缩容1/2，缩容容量不能为0，否则无法扩容
	if d.size == d.GetCap()/4 && d.GetCap()/2 != 0 {
		d.resize(d.GetCap() / 2)
	}
	return e, nil
}

func (d *Deque[E]) resize(capacity int) {
	newData := make([]E, capacity, capacity)
	for i := 0; i < d.size; i++ {
		newData[i] = d.data[(d.front+i)%cap(d.data)]
	}
	d.data = newData
	d.front = 0
	d.tail = d.size
}

func (d *Deque[E]) String() string {
	var sb strings.Builder
	sb.WriteString(fmt.Sprintf("Queue: size = %d , capacity = %d\n", d.size, d.GetCap()))
	sb.WriteString("front [")
	for i := 0; i < d.size; i++ {
		e := d.data[(d.front+i)%cap(d.data)]
		sb.WriteString(fmt.Sprintf("%+v", e))
		if i != d.size-1 {
			sb.WriteString(", ")
		}
	}
	sb.WriteString("] tail")
	return sb.String()
}
